#include <iostream>
#include "vector"
#include "map"
#include <unordered_map>
#include <stack>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <queue>
#include <cctype>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        //不同路径升级版 加了障碍物
        // dp[i][j]代表到达(i,j)的路径条数
        //递归方程dp[i][j]=dp[i-1][j]+dp[i][j-1]
        //初始化 因为只能往右和往下 所以上边界和左边界可以初始化为1
        //但注意的是如果有障碍物 后面全0
        vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));
        bool isobstac = false; //是否有障碍物
        for (int i = 0; i < obstacleGrid.size(); i++)
        {
            if (obstacleGrid[i][0] == 1)
            {
                isobstac = true;
            }
            if (!isobstac)
            {
                dp[i][0] = 1;
            }
            else
            {
                dp[i][0] = 0;
            }
        }
        isobstac = false;
        for (int j = 0; j < obstacleGrid[0].size(); j++)
        {
            if (obstacleGrid[0][j] == 1)
            {
                isobstac = true;
            }
            if (!isobstac)
            {
                dp[0][j] = 1;
            }
            else
            {
                dp[0][j] = 0;
            }
        }
        //初始化完毕
        for (int i = 1; i < obstacleGrid.size(); i++)
        {
            for (int j = 1; j < obstacleGrid[0].size(); j++)
            {
                if (obstacleGrid[i][j] == 1)
                {
                    dp[i][j] = 0;
                }
                else
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};

int main()
{
    Solution s;
    vector<int> bills = {5, 5, 10, 10, 20};
    cout << s.lemonadeChange(bills);
    return 0;
}